package demo1;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @Author liangzai
 * @Description:
 */
public class Training {
    //组合总和 2
    public  List<List<Integer>> combinationSum2(int[] candidates, int target) {

        List<List<Integer>> result = new ArrayList<>();//定义结果集
        if(candidates==null || candidates.length==0){
            return result;//如果不存在candidates或者candidates中的内容为0个时
        }

        //统计每个元素出现的次数（通过HashMap进行实施），避免后续通过回溯算法调用到同一样的组合结果。
        Map<Integer,Integer> elementMap = new HashMap<>();
        for(int candidate:candidates){
            elementMap.put(candidate,elementMap.getOrDefault(candidate,0)+1);
        }

        //对element的数据进行排序，正排（通过List进行排序）
        List<int[]> freq = new ArrayList<>();
        for(Map.Entry<Integer,Integer> entry:elementMap.entrySet()){
            freq.add(new int[]{entry.getKey(),entry.getValue()});//每个数组无数，0位置上代表的是数据，1位置上代表的是当前数出现的次数
        }

        freq.sort((a,b)->a[0]-b[0]);//对freq进行从小大到进行排序，对后续递归调用的剪枝提前准备。

        dfs(freq,0,target,new ArrayList<>(),result);

        return result;

    }

    //递归处理
    public void dfs(List<int[]> freq,int pos,int rest,List<Integer> path,List<List<Integer>> result){

        //得到组合，反回结果值
        if(rest==0){
            result.add(new ArrayList<>(path));
            return;
        }

        //当处理值不满足条件时
        if(pos==freq.size() || freq.get(pos)[0]>rest){
            return;
        }

        //当不选择当前的数
        dfs(freq,pos+1,rest,path,result);
        //当选择当前的数
        int currentValue=freq.get(pos)[0];
        int currentValueLen=Math.min(rest/currentValue,freq.get(pos)[1]);

        for(int i=1;i<=currentValueLen;i++){
            path.add(currentValue);
            dfs(freq,pos+1,rest-i*currentValue,path,result);
        }
        //回溯
        for(int i=1;i<=currentValueLen;i++){
            path.remove(path.size()-1);
        }
    }

    //买卖股票的最佳时机含手续费
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        if(n==1){
            return 0;
        }
        int[] dp1 = new int[n];
        int[] dp2 = new int[n];
        dp1[0] = -(prices[0]+fee);
        dp2[0] = 0;
        for (int i = 1; i < n; i++) {
            dp1[i] = Math.max(dp1[i-1],dp2[i-1]-prices[i]-fee);
            dp2[i] = Math.max(dp2[i-1],dp1[i-1]+prices[i]);
        }
        return Math.max(dp1[n-1],dp2[n-1]);
    }

    //买卖股票的最佳时机 3
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if(n<=1) {
            return 0;
        }
        int[][] dpf = new int[n][2];
        int[][] dpg = new int[n][3];
        dpf[0][0] = -prices[0];
        for (int i = 1; i < n; i++) {
            dpf[i][0] = Math.max(dpf[i-1][0],dpg[i-1][0]-prices[i]);
            dpf[i][1] = Math.max(dpf[i-1][1],dpg[i-1][1]-prices[i]);
            dpg[i][1] = Math.max(dpg[i-1][1],dpf[i-1][0]+prices[i]);
            dpg[i][2] = Math.max(dpg[i-1][2],dpf[i-1][1]+prices[i]);
        }
        return Math.max(dpg[n-1][0],Math.max(dpg[n-1][1],dpg[n-1][2]));
    }
}
